package org.idea.iedis.framework.server.datastruct.zset;


import java.util.Random;

/**
 * 通过双向链表 支持插入的时候可以按照得分进行排序
 * 但是存在问题：
 * 1.查询性能较低，需要从头到尾进行遍历,查询数据的复杂度为O(n)
 * 2.写入数据的复杂度为O(n)
 * 3.查询得分大于某个固定值的时候，需要从头到尾遍历 ，复杂度为O(n)
 * 好处：一种数据结构，实现简单
 *
 *
 * @Author linhao
 * @Date created in 5:00 下午 2021/5/7
 */
public class EntrySet {

    public EntryItem head;

    public EntrySet(EntryItem entryItem) {
        this.head = entryItem;
    }

    private void headInsert(EntryItem entryItem) {
        this.head = entryItem;
        this.head.pre = null;
    }

    private void headBeforeInsert(EntryItem entryItem) {
        EntryItem oldItem = this.head;
        this.head = entryItem;
        this.head.pre = null;
        this.head.next = oldItem;
        oldItem.pre = this.head;
    }

    /**
     * 默认是按照score从小到大排序
     *
     * @param entryItem
     * @return
     */
    public EntryItem addOne(EntryItem entryItem) {
        //头部插入
        if (head == null) {
            this.headInsert(entryItem);
            return entryItem;
        }
        //头前插入
        if (head.score > entryItem.score) {
            this.headBeforeInsert(entryItem);
            return entryItem;
        }

        EntryItem oldItem = head.next;
        EntryItem preItem = head;
        while (oldItem != null) {
            if (oldItem.score > entryItem.score) {
                preItem = oldItem.pre;
                preItem.next = entryItem;
                entryItem.pre = preItem;
                entryItem.next = oldItem;
                oldItem.pre = entryItem;
                break;
            }
            preItem = oldItem;
            oldItem = oldItem.next;
        }
        //第二项插入 或者 最后一项插入
        if (oldItem == null) {
            preItem.next = entryItem;
            entryItem.pre = preItem;
        }
        return entryItem;
    }

    public boolean isContain(String key) {
        if (key == null || key == "") {
            System.err.println("参数异常");
            return false;
        }
        EntryItem temp = head;
        while (temp != null) {
            if (key.equals(temp.key)) {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    public void display() {
        EntryItem temp = head;
        while (temp != null) {
            System.out.println("key:" + temp.key + ",score:" + temp.score);
            temp = temp.next;
        }
        System.out.println("====");
    }

    public static void main(String[] args) throws InterruptedException {
        EntrySet entrySet = new EntrySet(null);
        for (int i = 0; i < 20; i++) {
            entrySet.addOne(new EntryItem("key" + 6, new Random().nextInt(100), null, null));
        }
        entrySet.display();
        System.out.println("end");
    }

}
